class Solution {
    public int appearNums(int[] nums, int target) {
        int count = 0;
        int index = Arrays.binarySearch(nums, target);
        if (index < 0) {
            return 0;
        }
        for (int i = index; i >= 0; i--) {
            if (nums[i] == target) {
                count++;
            } else {
                break;
            }
        }
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
            } else {
                break;
            }
        }
        return count;
    }

    public int maximumSwap(int num) {
        int[] sortNum = new int[9];
        int[] originNum = new int[9];
        int tmpNum = num;
        int index = 8;
        while (tmpNum != 0) {
            int tmp = tmpNum % 10;
            if (tmp >= sortNum[0]) {
                for (int i = 8; i > 0; i--) {
                    sortNum[i] = sortNum[i - 1];
                }
                sortNum[0] = tmp;
            } else {
                int i = 0;
                while (i < 8) {
                    if (tmp <= sortNum[i]) {
                        i++;
                    } else {
                        break;
                    }
                }
                sortNum[i] = tmp;
            }
            originNum[index] = tmp;
            index--;
            tmpNum = tmpNum / 10;
        }
        for (int i = 0; i < 9 - index - 1; i++) {
            originNum[i] = originNum[i + index + 1];
        }

        // 寻找排序后数组和原数组的两个交换位置
        // 即第k大的数字应当在第k位上
        int swpNumPos1 = -1, swapNum = Integer.MAX_VALUE;
        int swpNumPos2 = -1;
        for (int i = 0; i < 9; i++) {
            if (originNum[i] != sortNum[i]) {
                swpNumPos1 = i;
                swapNum = sortNum[i];
                break;
            }
        }
        for (int i = 7 - index; i >= 0; i--) {
            if (originNum[i] != sortNum[i] && originNum[i] == swapNum) {
                swpNumPos2 = i;
                break;
            }
        }
        if (swpNumPos1 < 0 || swpNumPos2 < 0) {
            return num;
        }

        // 交换原数字数组两位
        originNum[swpNumPos1] = originNum[swpNumPos1] ^ originNum[swpNumPos2];
        originNum[swpNumPos2] = originNum[swpNumPos1] ^ originNum[swpNumPos2];
        originNum[swpNumPos1] = originNum[swpNumPos1] ^ originNum[swpNumPos2];

        int sum = 0;
        for (int i = 0; i < 8 - index; i++) {
            sum = sum * 10 + originNum[i];
        }
        return sum;
    }

    public int hanmingWeight(int num) {
        int count = 0;
        while (num != 0) {
            count += (num & 1);
            num >>= 1;
        }
        return count;
    }
}